package com.yxp.offer;

/**
 * @Auther : yxpweb
 * @Date : 2021/8/22 10:18
 * @Description: 剑指 Offer 46. 把数字翻译成字符串
 */
public class Problem46 {

    public static void main(String[] args) {
        Problem46 problem46 = new Problem46();
        System.out.println(problem46.translateNum(18822));
    }

    /**
     * 明确状态转移，并且得到状态转移方程
     * 最后一个数字可以翻译的情况和最后2个数字可以翻译的情况
     * @param num
     * @return
     */
    public int translateNum(int num) {
        if (num < 0) {
            return 0;
        }
        String s = String.valueOf(num);
        char[] chars = s.toCharArray();
        int[] numbers = new int[chars.length];
        int[] sums = new int[chars.length + 1];
        sums[0] = 1;
        sums[1] = 1;
        for (int i = 0; i < chars.length; i++) {
            numbers[i] = Integer.valueOf(String.valueOf(chars[i]));
        }
        for (int i = 1; i < numbers.length; i++) {
            sums[i + 1] = sums[i];
            int a = numbers[i - 1];
            int b = numbers[i];
            if (a >= 1 && a <= 2 && a * 10 + b <= 25) {
                sums[i + 1] = sums[i] + sums[i - 1];
            }
        }
        return sums[chars.length];
    }

    //    作者：jyd
    //    链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
//    public int translateNum(int num) {
//        String s = String.valueOf(num);
//        int a = 1, b = 1;
//        for (int i = 2; i <= s.length(); i++) {
//            String tmp = s.substring(i - 2, i);
//            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
//            b = a;
//            a = c;
//        }
//        return a;
//    }



}
